//给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
//请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。


//head = [1, 2, 3, 4, 5], left = 2, right = 4
//输出：[1, 4, 3, 2, 5]

//方案一：递归
//想法： 先把大链表的 2号节点和4号节点进行翻转 得到[4, 3 ,2 ]
//如果我们选择小链表[2, 3, 4] 进行反转  则反转1和 3号节点进行反转
//如果再抛去第二号节点进行反转 则是反转子链表的 1号 和 2号节点
//边界条件 左右区间为 1


//方案二：非递归
//整体思想是：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。

#include "List.h"

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        //方法一：递归
        if (left == 1 && right == 1) return head;
        if (left != 1)
        {
            head->next = reverseBetween(head->next, left - 1, right - 1);
        }
        else
        {
            ListNode* tail = head->next, * newnode;
            newnode = reverseBetween(head->next, left, right - 1);
            head->next = tail->next;
            tail->next = head;
            head = newnode;
        }
        return head;


        ////方案二： 非递归
        //ListNode* dummy = new ListNode(-1);
        //dummy->next = head;
        //ListNode* pre = dummy;
        //for (int i = 0; i < left - 1; i++) //找到需要反转子链表的第一个节点前面那个节点
        //{
        //    pre = pre->next;
        //}
        //ListNode* cur = pre->next; //记录反转子链表的第一个节点
        //ListNode* next;
        //for (int i = 0; i < right - left; i++)
        //{
        //    next = cur->next;//记录反转子链表的第一个节点的下一个节点
        //    cur->next = next->next;//反转子链表的第一个节点的下一个节点 等于 下一个节点的下一个节点
        //    next->next = pre->next;// 反转子链表的第一个节点的下一个节点的下一个节点 等于 反转子链表的第一个节点
        //    pre->next = next; //反转子链表的第一个节点前面那个节点的下一个节点等于反转子链表的第一个节点
        //}
        //return dummy->next;
    }
};